/**
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
 */


// 1. 类似冒泡排序 (时间复杂度O(N2))
// 两两比较，如果前者是偶数，就交换位置
var exchange = function(nums) {
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = 0; j < nums.length - i - 1; j++) {
            if (nums[j] % 2 === 0 && nums[j + 1] % 2 !== 0) {
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
            }
        }
    }
    return nums;
};

// 2. 双指针
var exchange = function(nums) {
    let [i, j] = [0, nums.length - 1];
    while (i < j) {
        if (nums[i] % 2 !== 0) {
            i++;
            continue;
        }
        if (nums[j] % 2 === 0) {
            j--;
            continue;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]]

        // 增加下面两行进一步优化，交换后i是奇数，j是偶数，直接跳过
        i++;
        j--;

    }
    return nums;
};

// 3. 快慢指针
var exchange = function(nums) {
    let low = fast = 0;
    while (fast < nums.length) {
        if (nums[fast] % 2) {
            [nums[low], nums[fast]] = [nums[fast], nums[low]];
            low++;
        }
        fast++;
    }
    return nums;
};